JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Round Tables General Career Discussions Question
 Question | Reply I was asked these questions during a recent interview. Q1: Given a 2 dimensional array of characters and a dictionary, extract all the meaningful words from the array. The words can be positioned horizontally, vertically or diagonally within the array. I was asked to come up with an efficient algorithm.. Q2: In a single nested for loop, determine if a filled in sudoku is a valid solution.Ny ideas on how to go abt?
 Re: Question (response to post by Nukem) | Reply I'm not sure I want to spend brain power on that at the moment, but how can you have a "single nested for loop"?
 Re: Question (response to post by Nukem) | Reply For the second one, I would just have an outer for loop that increments from 0 to 3.If the for loop value is 0, check all rows to see that each row uses the numbers 1-9 once.If the for loop value is 1, check all columns to ensure that each column uses 1-9 once.If the for loop value is 2, check each of the 9 3x3 subgrids to make sure that they use 1-9 only once.IIRC, these are all the checks of a valid suduko placement.
 Re: Question (response to post by EmperorofUnivrs) | Reply But then, can't you just not use a loop at all? How is it helping here? Instead of```if (x == 0) { check case A } else if (x == 1) { check case B } else { check case C } ```the code```check case A check case B check case C ```seems a lot shorter.
 Re: Question (response to post by Minilek) | Reply My guess is they really are looking for something like```for (int i=0; i<3; i++) for (int j=0; j<3; j++) { int hor = 0; int vert = 0; int square = 0; for (int x=0; x<3; x++) for (int y=0; y<3; y++) { hor |= 1<< grid[3*i + j][3*x + y]; vert |= 1<< grid[3*x+y][3*i+j]; square |= 1<
 Re: Question (response to post by Minilek) | Reply He said nested for loops... But I agree with you.I don't like it when odd constraints are placed on my programming. I'd much rather have the interviewer say "do such and such with this time complexity"
 Re: Question (response to post by Nukem) | Reply On the first, what do you mean by "efficient algorithm"? The most trivial algorithm I can think is not that inneficient
 Re: Question (response to post by Malkava) | Reply The first I thought of was Aho-Corasick on each row/column/diagonal.
 Forums Round Tables General Career Discussions Question Previous Thread  |  Next Thread