prolific.coder
BAN USER- 0of 0 votes
AnswersGiven a book find out the number of times each word appeared. Upon clarification I was told the following things 1. punctuations should be removed 2. case sensitive 3. assume book is given as a huge string to the function prototype 4. Words need not be ordered in any way
- prolific.coder| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test String Manipulation - 0of 0 votes
AnswersImagine you have a hard disk with blocks of memory 1..n. Files can be stored on one or more of these blocks. If a file spans more than one block, you can know the next block by querying the current block. Also you can query block with Node.isEmpty() method to know if it has any data. The system has a table which has a list of the files and the first node of each file. But that table has been corrupted, reconstruct that table. The names of the files are immaterial and you can get the index as well as the name of the nextblock when you query for Node.NextBlock()
- prolific.coder| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test
@witty not sure if I understood your comment correctly. But each ship in a battleship game occupies more than one square. A ship is not sunk until all the cells/blocks of it are hit. en.wikipedia.org/wiki/Battleship_(game)
In my case when the ship is hit, I am just remove the hash/set value from the array. In code, I will have a check to see if there are no remaining values and return SUNK if true.
cid-b3e432122fdd837d.photos.live.com/self.aspx/public/119.jpg in this case a pic can be lot more explanatory
- prolific.coder March 26, 2011Input Output explanation
1. 1->2->2->3->4 1->2->3->4 the sanity path
2. 1->1->2->3 1->2->3 border case duplicate at head
3. 1->2->3->3 1->2->3 border case duplicate at tail
4. 1->1->1->1 1-> all duplicates
5. 1->2->3->4 1->2->3->4 no duplicates
6. 1->2->3->2 1->2->3 duplicates in alternative positions (not consecutive)
7. Int.Min-1->2->1->Int.Max+1 2->1 test to make sure that the linked list structure handles numbers out of int range (the question didn't specify the range)
8. 1->2->1->2->3->3 1->2->3 each node has a duplicate
9. -1->0->1 throw exception should verify that erroroneous data is not being handled
10. 2->3->3->2->1 verify that the head is 2 making that the spec is being met
11. 1->1->1->1->1->1->1->2 1->2 just one non duplicate
12. test for a huge linked list that would potentially overflow memory and verify than the behavior is predictable
Things to consider here
1. How large is n?
2. How many ships should we accomidate?
3. Error checks. is the ship partially/fully outside the battleground :)
Assuming all normal cases
ships are numbered 1 to m
For efficiency I would assume/create a hash function which takes in i,j and returns the cell in constant time.
I would use two data structures, one int 2D matrix, 0 indicates no ship a number indicates the ship number, the other data structure is a list/array of sets. Each list contains the hashed values of the ship locations.
attack(i,j) can result in three cases
1. there is no ship - we ignore (unless we don't duplicate hits)
2. there is a ship, lets say 2, now go to the 2nd list and delete the hash corresponding to this cell. If the list is now empty return sunk
2a. if the list not empty continue
With this solution all operations are constant, including declaring that a ship is sunk. We can also improve this to know if the game is over
quick sort would make the coplexity n(logn)
- prolific.coder September 09, 2010We can't store bunch of mappings for each digit i.e 9, 60,4 are all superfluous. If you want to argue for it, I can argue that I'd store all the mappings from 1-5000 in an array, precompute them and return values in constant time.
- prolific.coder August 12, 2010Well you never knew. I once had 4 round of interview and got a reject, so I thought if I don't see the hiring manager its not good but 4 months back I talked with hiring manager and 2 levels up :) But even then I was not offered, so generalizations aren't working, keep us posted of the result. And I am pretty near to MS main campus.. we can meet up some time..
- prolific.coder August 12, 2010<pre lang="java" line="1" title="CodeMonkey2481" class="run-this">//To covert a sorted doubly linked list to binary search tree
//Lots of boiler plate for DLL and BST for the actual code is only 5 lines
class DoubleLinkedListNode{
int item;
DoubleLinkedListNode next;
DoubleLinkedListNode prev;
public DoubleLinkedListNode(int item) {
this.item=item;
next=null;
prev=null;
}
@Override
public String toString(){
StringBuilder sb=new StringBuilder();
if(this.prev==null)
sb.append("X--");
else
sb.append(this.prev.item+"--");
sb.append(this.item);
if(this.next==null)
sb.append("--X");
else
sb.append("--"+this.next.item);
return sb.toString();
}
}
class DoubleLinkedList{
int size;
DoubleLinkedListNode head;
public DoubleLinkedListNode getNode(int num){
if(num<0)
return null;
DoubleLinkedListNode cur=head;
int i=0;
while(cur!=null){
if(i==num)
return cur;
i++;
cur=cur.next;
}
return cur;
}
}
class BinarySearchTreeNode{
int item;
BinarySearchTreeNode leftChild;
BinarySearchTreeNode rightChild;
public BinarySearchTreeNode(int item) {
this.item=item;
leftChild=null;
rightChild=null;
}
public BinarySearchTreeNode(){}
@Override
public String toString(){
StringBuilder sb=new StringBuilder();
if(this.leftChild==null)
sb.append("X--");
else
sb.append(this.leftChild.item+"--");
sb.append(this.item);
if(this.rightChild==null)
sb.append("--X");
else
sb.append("--"+this.rightChild.item);
return sb.toString();
}
}
class DLLtoBST {
public static void main(String args[]){
DoubleLinkedListNode d4=new DoubleLinkedListNode(13);
DoubleLinkedListNode d3=new DoubleLinkedListNode(11);
DoubleLinkedListNode d2=new DoubleLinkedListNode(9);
DoubleLinkedListNode d1=new DoubleLinkedListNode(7);
DoubleLinkedListNode d0=new DoubleLinkedListNode(3);
d0.next=d1;d0.prev=null;
d1.prev=d0;d1.next=d2;
d2.prev=d1;d2.next=d3;
d3.prev=d2;d3.next=d4;
d4.prev=d3;d4.next=null;
DoubleLinkedList dll=new DoubleLinkedList();
dll.head=d0;
DLLtoBST db=new DLLtoBST();
BinarySearchTreeNode root =db.createBST(dll,0,4);
System.out.println(root);
System.out.println(root.leftChild);
System.out.println(root.leftChild.rightChild);
System.out.println(root.rightChild);
System.out.println(root.rightChild.rightChild);
}
private BinarySearchTreeNode createBST(DoubleLinkedList dll, int start, int end) {
BinarySearchTreeNode root= new BinarySearchTreeNode();
if(start<=end){
int mid=(start+end)/2;
DoubleLinkedListNode cur=dll.getNode(mid);
root=new BinarySearchTreeNode(cur.item);
root.leftChild=createBST(dll, start, mid-1);
root.rightChild=createBST(dll,mid+1,end);
}
return root;
}
}
</pre><pre title="CodeMonkey2481" input="yes">
</pre>
After looking at the problem I thought its not that difficult but I had like 5-6 bugs in my implementation and it took around 2 hours to get this code.
Idea is for each element in matrix find if it matches the first word, if it matches then we have to look in 4 directions. If there is match in that direction proceed till we are end of the string. If match return true if not return false. We have or || all the directions because the string can be in any of 4 directions. Also Math.abs takes care of wrap around (this was my big bug)
package com.code.prolificcoder;
public class StringFinder {
enum Direction{up,down,left,right};
public static void main(String args[]){
char[][] ar=new char[][]{{'m','s','s','h'},
{'a','t','c','i'},
{'p','d','a','n'},
{'s','a','t','h'},
};
String str="tcia";
StringFinder sf=new StringFinder();
System.out.print(sf.stringFinder(ar,str));
}
private boolean stringFinder(char[][] ar, String str) {
int size=ar.length;
if(str.length()>size+1) return false;
int k=0;
char[] charArray=str.toCharArray();
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
if(ar[i][j]==charArray[k])
return isMatch(ar,charArray,i,Math.abs((j+1)%size),k+1,Direction.right)||
isMatch(ar,charArray,Math.abs((i+1)%size),j,k+1,Direction.down)||
isMatch(ar,charArray,Math.abs((i-1)%size),j,k+1,Direction.up)||
isMatch(ar,charArray,i,Math.abs((j-1)%size),k+1,Direction.left);
return false;
}
private boolean isMatch(char[][] ar, char[] charArray, int i, int j, int k, Direction dir) {
int size=ar.length;
if(k==charArray.length-1)
{
if(ar[i][j]==charArray[k]) return true;
else return false;
}
if(ar[i][j]==charArray[k]){
if(dir==Direction.down)
i=Math.abs((i+1)%size);
else if(dir==Direction.right)
j=Math.abs((j+1)%size);
else if(dir==Direction.left)
j=Math.abs((j-1)%size);
else //dir==Direction.up
i=Math.abs((i-1)%size);
return isMatch(ar,charArray,i,j,k+1,dir);
}
return false;
}
}
<pre lang="java" line="1" title="CodeMonkey20076" class="run-this">class Caller {
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
Caller c=new Caller();
System.out.print(c.convertToRoman(1681));
}
class Romans{
int deciValue;
char value;
Romans(int deciValue, char value){
this.deciValue=deciValue;
this.value=value;
}
}
public String convertToRoman(int num)
{
StringBuffer sb=new StringBuffer();
Romans[] romans = getRomans();
for(int i=0;i<romans.length;i++)
{
int count=num/romans[i].deciValue;
num=num-(romans[i].deciValue*count);
while(count !=0){
sb.append(romans[i].value);
count--;
}
}
return sb.toString();
}
private Romans[] getRomans() {
Romans roman1=new Romans(1000,'M');
Romans roman2=new Romans(500,'D');
Romans roman3=new Romans(100,'C');
Romans roman4=new Romans(50,'L');
Romans roman5=new Romans(10,'X');
Romans roman6=new Romans(5,'V');
Romans roman7=new Romans(1,'I');
Romans[] romans=new Romans[]{roman1,roman2,roman3,roman4,roman5,roman6,roman7};
return romans;
}
}
</pre><pre title="CodeMonkey20076" input="yes">1681
</pre>
If we are only considering two number combinations i.e. lets say the range is 12 to 40 12+13=25 but not 12+13+14=39. The algorithm is as follows
public void printCombinations(int num1,int num2)
{
for(int i=num1;i<num2;i++)
{
int range=num2=num1;
for(int j=num1+1; j<=range;j++)
{
System.out.println(num1+""+j+num1+"j"+(num1+j));//this could not compile but //idea is to get tostring of all the numbers excpet the last expression
}
}
}
The only idea I can think of to include more than 2 numbers is to do some kind of meta programming and including another level of for loop based on 3num1+3<num2. But in java I wont bother doing it.
- prolific.coder August 05, 2010For this question, I got baffled because the answer is like so straight forward create a hash... I assumed he don't want that solution and after saying hash as my first thought gave him several approaches but then he wanted me to code in IDE (we were remoting) then I thought sticking to hash solution because its simple. He even allowed me to use library functions like str.Split(I assumed for a while that I shouldn't). I got the solution working. I didn't handle special characters and spaces due to lack of time but I think its not bad for a phone interview.
- prolific.coder July 13, 2010I gave the following solution. He didn't ask me to code just give algorithm
1. Create a hash function that sorts the words in alphabetic order, we will use this for our hashing
2. For each word in the dictionary - use the above hash if there is no collision create a new entry, if there is a collision add the word to the list of values.
3. Ignore/remove all entries of size 1. Now we have the list of all anagrams.
Programming pearls have a slightly different solution but I think basically both are same and if I were the interviewer I would have appreciated the original thought rather than repeat a bookish solution. But I don't think he liked it as much as I did :)
@abc I am not sure I followed your example correctly. {1,3,2,4,5,4,2}
Number of elements lesser or equal to 1=0,3=3,2=3,4=5,5=6,4=5,2=3.. am I missing something here?
Explaining my algorithm
1. Create a charhash with the characters T with <character,count>
2. Initiliaze minSoFar=str.length and minstart and maxstart
3. traverse the String S i to S.length
3.1 If S[i] in present in hash
3.1.1 Create a new temp hash cloning/copying the charhash
3.1.2 Remove this char(S[i]) from the temp hash if the count is 1 or reduce the count
3.1.3 Initialize a window size to characters T.length.
3.1.4 traverse the string starting from j=i+1 to i+1+windowsize
3.1.4.1 if tempcharhash contains the str[j]
3.1.4.1.1 remove the char from the tempcharhash if count is 1 here also check if the tempcharhash is empty
3.1.4.1.2 if yes update maxsofar,minstart and minend values and break
3.1.4.1.3 reduce the count if tempcharhash[str[j]] count is not 1
3.1.4.2 if the str[j] is not present increase the window size
3.2 Return minstart and minend
Though I am sure my solution is not elegant it works and it is O(n). The inner for loop in the code is a small one(i think I can further halting points) and AFAIK it does make the algorithm larger than O(n). I got idea for this code from the largest sum problem(-ve numbers included) in programming pearls. Here goes the code, let me know your thoughts.
Code is not being allowed here so I put it on ideone
http: //ideone.com / Z3TDm
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CareerCupProblems
{
class Program
{
static void Main(string[] args)
{
Program p=new Program();
string chars = "adbb";
string str = "ajfblkdasb";
int[] ar = p.MinimumWindow(chars, str);
Console.WriteLine(ar[0] + " " + ar[1]);
}
//http://www.careercup.com/question?id=3268664
//Finding the minimum window in a string in which we can find all the chars in another string
public int[] MinimumWindow(string chars, string str)
{
Dictionary<char, int> charhash = new Dictionary<char, int>();
foreach (char c in chars)
{
if (charhash.ContainsKey(c))
charhash[c]++;
else
charhash.Add(c, 1);
}
int minSoFar = str.Length;
int minStart = 0, minEnd = 0;
for (int i = 0; i < str.Length; i++)
{
if (charhash.ContainsKey(str[i]))
{
Dictionary<char, int> tempCharHash = new Dictionary<char, int>(charhash);
if (tempCharHash[str[i]] == 1)
tempCharHash.Remove(str[i]);
else
tempCharHash[str[i]]--;
int restCount = chars.Length;
for (int j = i + 1; j < i+1+restCount && j < str.Length; j++)
{
if (tempCharHash.ContainsKey(str[j]))
{
if (tempCharHash[str[j]] == 1)
{
tempCharHash.Remove(str[j]);
if (tempCharHash.Count == 0)
{
if (minSoFar > j - i)
{
minSoFar = j - i;
minStart = i; minEnd = j;
}
break;
}
}
else
tempCharHash[str[j]]--;
}
else restCount++;
}
}
}
return new int[] { minStart, minEnd };
}
}
}
I got the same question during a Microsoft technical screen and the guy is like I don't want you to use a count(q.Count) on the queue! Nor to check for queue.isEmtpy(). So my solution relied on catching the exception and handling it and I had a slight bug in my implementation which I discovered but wasn't able to fix. Guess what.. reject! We think the world is sane and we are programming for objects/collection and can count them, apparently we can't :)
- prolific.coder July 07, 2010Probably an similar approach to S but using hash. I generally prefer hashes to BST's or other trees because hashes are built into the language and we need not create a seperate structure. Pseudo code is as follows
1. create a hash hs of <string,int>
2.string str=""
3.while(( str=getNextWord())!=EOF)
3A. if hs contains str increment the value of hs[str]
3B. if not create a new key value pair with hs.add(str,1)
4.Create a linked list by traversing hs
This solution would have o(n) complexity and extra space required for hashing.
While this solution might be what we do in 'real' world the interviewer might want us to use the isEqual() function then S's solution should work just fine.
I guess the first question we ought for this is what are we trying to do here and what the constraints. Insertion,deletion, lookup(for sure) and space considerations. Based on that we can discuss various approaches. Search youtube for Lecture 25 | Programming Abstractions (Stanford) she talks a lot about this
- prolific.coder June 23, 2010The code is not running here somehow. But running in my IDE pretty correctly. This is working for all the cases I tested. If you find bugs lemme know.
- prolific.coder June 23, 2010<pre lang="java" line="1" title="CodeMonkey41137" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Hashtable;
import java.util.List;
import java.util.Scanner;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
Main m= new Main();
ArrayList<Integer> mn=m.findMissingConsecutiveNumbers(new int[]{11,7,6,0,9,0,5});
for(Integer i: mn)
System.out.println(i);
}
//To find the missing numbers in a sequence of numbers
//Assuming that min is present and 0 as a sentinal element(the sequence will never have zero)
//Also that the array has enough space for missing elements
//eg: 10,8,9,5 are the numbers I am assuming there is empty space for 2 elems (6 and 7) at the end
//If I dont make this assumption I can't do it in place and in O(n) time
public ArrayList<Integer> findMissingConsecutiveNumbers(int[] numbers)
{
//Idea is to first find the minimum element and use it at the lowest index
int min=numbers[0],index=0;
ArrayList<Integer> missingNumbers=new ArrayList<Integer>();
//Find min element
for(int i=1;i<numbers.length;i++)
{
if(numbers[i]!=0&& min>numbers[i]){
min=numbers[i];
index=i;
}
}
//Put the min element at first
swap(numbers,0,index);
//Put the elements in their correct positions
for(int i=1;i<numbers.length;i++)
{
if(numbers[i]!=0 && numbers[i] != min+i){
swap(numbers, i,numbers[i]-min);
i--;
}
}
//Find the missing elements and add them to a list
for(int i=1;i<numbers.length;i++)
{
if(numbers[i]==0)
missingNumbers.add(i+min);
}
return missingNumbers;
}
private void swap(int[] ar, int i, int j) {
int temp=ar[i];
ar[i]=ar[j];
ar[j]=temp;
}
}</pre><pre title="CodeMonkey41137" input="yes">1
2
10
42
11
</pre>
Improving on mayank's solution and using only bitset. I don't see the need of hash if all we are doing is printing out.
public void PrintNumbers(String file,int sum) throws FileNotFoundException
{
BitSet bs= new BitSet(sum);
//HashSet<Integer> hash = new HashSet<Integer>();
Scanner s= new Scanner(new File(file));
while(s.hasNextInt()){
int x=s.nextInt();
if(x<=sum){
if(bs.get(sum-x)==true){
//if(hash.contains(sum-x)){
System.out.println(x +" "+(sum-x));
bs.set(sum-x, false);//To take care of duplicates
}
else
bs.set(x);
}
}
}
I don't know about other languages but in C#, a good idea would be to use an inner class to create an instance of the parent class.
Since locks on placed on classes our code will be thread safe. Copying code from C# 3.0 design patterns
public class Singleton{
Singleton(){}//private constructor
class SingletonCreator{
static SingleTonCreator(){}
internal static readonly
Singleton UniqueInstance= new Singleton();
}
public static Singleton UniqueInstance {
get {return SingletonCreator.uniqueInstance;}
}}
These are some of the test cases I came up with, I covered many areas and there would many gaps but for an initial draft this would work.
How would you test a Keyboard?
Questions to ask:
1. What kind of keyboard is this? Computer, piano, iphone, or sliding keyboards (PDA)
a. Assuming its for computer
2. For whom is this keyboard for? Physically handicapped, what kind, blind, or normal, children?
a. Assuming its for a general human being
3. Who are these users? English, French, Russian?
a. English
4. What features should this keyboard support? Wireless, wired, multimediat support, volume control, Mac or PC (for win key)
a. Assume plain vanilla keyboard that you've seen from old days, without win key
5. Where is this keyboard used? On a laptop or desktop
a. Desktop
6. What format should of keys should the keyboard support? Qwerty or others?
a. Qwerty
7. Need a list of keys, positions they are in, times they come up and the space each of them occupy
a. Its not unusual to have 1 ctrl key and one mac key etc.
b. Assume its given
8. Any other non-functional requirements?
a. Lag between a keystroke and the time the display is updated
b. Ergonomics that need to considered (curved, split keyboards)
c. What configurations of hardware should it support?
d. Do we need to provides pinheads on FJ?
9. What is the motive of this testing are we doing it in a factory or somewhere else?
a. This determines the level of automation required.
b. Do we test each and every keyboard or only a sampling of them.
10. Are we testing just hardware or hardware + software?
a. Eg. The work of the keyboard when shift+a is pressed is to send the corresponding signal
i. Software is free to interpret this according its specifications.
Sanity test case(Happy path)
1. Assuming a base case are ALL the keys being able to send appropriate signals to the software?
a. This should include the alphabet keys, the control keys (ALT,ctrl,page up, page down..), functional keys (F1-F12), special keys (win key, numlock,scrolllock etc.), arrow keys
2. All the composite keys able to send appropriate signals? (%,^ etc)
a. Pressing shift and composite keys
Functional testing
1. Divide the problem area into equivalence classes.
a. Eg. All the alphabet keys a-z, all numeric keys, special keys, media keys etc..
b. This reduces the number of test cases to be performed and provides us with confidence
2. Find the boundaries (might not make sense for this problem)
a. We need to find boundaries in terms of hardware signals and check there
b. The above equivalence classes might also need to reconsidered.
3. Combinatorial testing - Shift key is notorious for this - (but I think hardware need not be concerned with this, the software that interprets a key should consider these)
a. We need to create a subset of all valid and invalid combinations and check for the accepted output.
b. EG. Each of the shift key is working? Does it making capitals, getting right symbol from
c. Combinations of different keys (ctrl+shift+del, ctrl+alt+del)
4. What happens when a key is pressed 100 times consecutively 100000 times?
Structural testing (not possible unless we are looking at the hardware code)
Nonfunctional testing
1. Accessibility - how useful is the keyboard to a blind person or partially blind?
a. How about a person with a single hand or missing/dysfunctional fingers
b. Are children and are old people able to use it? How much pressure does a key require
c. Are the keys visible are clearly comprehendible? How about partially blind people?
2. Usability testing
a. Does using the keyboard cause pains? After how much usage?
b. Does the keyboard have a curved design (ergonomics)
c. Does the keyboard have a slanting feature (to raise it to a tilt)
3. Performance testing
a. Is the lag is the accepted range?
i. How about a fast typer?
ii. How about a gamer?
iii. How about an automated machine
b. Is the lag same for all classes keys? Composite keys or when in combinations?
c. The interval at which a key should count as a second stroke? (functional test)
4. Stress testing
a. How does the keyboard function in cases of short spurts of large volume of signals?
5. Volume testing
a. How does it behave in case of large volume of data
6. Compatibility testing
a. Does the keyboard support the configurations it supposed to support?
b. How about a very old computer?
c. Does it support a USB connection or PC2 connection or both? Does the connection change any of its other facets (performance, stress etc)
7. Durability-
a. After how much use the keys content fade away, is it acceptable?
b. If the keyboard falls, what height its okay to break?
c. How much weight it should be
8. Maintenance-
a. Is the keyboard cleanable
b. If there is a problem with it, can it be opened and closed by a technician?
c. Does it have identifying information so that a customer can request support for it?
9. Statutory
a. Does it have proper warnings (parts can be choke children etc?)
b. Does it adhere to standards?
there are people who are just not fit for testing and for that matter anything, that just type crap since they have a keyboard(xin hu) - test if the keyboard is working for them too.
The solution for this problem involves us thinking in terms of Base 26 notation like Hexadecimal (which is 16). I am trying to remember the way we convert Base 16 to Base 10. We could apply the similar logic.
After writing I kind of remember trying to get the modulo of the number any may be first solution leads to that.
This solution is not mine but mayank on cc chat. He says that the wooden blocks L can be tilted so that we could use their hypotenuse which is definetely larger than L. It does not matter if the block is a rectangle or square shaped the diagonals is larger and we use them to cross the water.
- prolific.coder May 20, 2010Okay I got solution that takes in any array and returns it without duplicates in C# -
public T[] RemoveDuplicates<T>(T[] elems)
{
HashSet<T> uniques = new HashSet<T>();
foreach (var item in elems)
uniques.Add(item);
elems = new T[uniques.Count];
int cnt = 0;
foreach (var item in uniques)
elems[cnt++] = item;
return elems;
}
I am thinking isn't there a generic way to handle this? i mean how abt creating a method that takes in any type of array and return it without duplicates?
- prolific.coder May 20, 2010The solution for an integer array
public int[] RemoveDuplicates(int[] elems)
{
HashSet<int> uniques = new HashSet<int>();
foreach (int item in elems)
uniques.Add(item);
elems = new int[uniques.Count];
int cnt = 0;
foreach (var item in uniques)
elems[cnt++] = item;
return elems;
}
Most of the people are like that :) It could be as simple as this - we might come to a solution that is not efficient or we might even be doing some simple mistakes coding our correct solution. It gives them a feeling that we are wrong all along.
- prolific.coder May 20, 2010That could work too, we create the hash set from first list and traverse the 2nd list. If the element is present in the hash set we remove it from the hashset if not we move on to the next element. At the end all the elements that are left in hash set are appended. The only problem I see with your solution is to handle duplicates in the second list. So we need to have a hashtable of some sort and mark it as seen before, unseen.
We could do that but I don't think the time complexity of the algorithm is not going to change much and in fact it could be better in my solution in regards to space.
There is a trick you can do with this problem. Since the interviewer did not specify in-place sorting.
1. First pass through the array and make a count of 0,1,2.
2. Then replace the array elements with those number of 0's, 1's and 2's
This is called counting sort if I am not wrong
This is a trick :) but they would want you do in place.
I am trying to follow your logic but couple things. There is no concept of a node "within" a block. Sorry if I misled you and the interviewer at the end of my solution was like aren't you wasting space with the additional flags array? So he is not linient with space constraints.. whatever.
- prolific.coder May 19, 2010Since no information about not using additional storage is given. I assume we can use HashSet to do the job of intersection.
Algorithm
1. Traverse list 1 and insert into hashset
2. Traverse list 2 and insert into hashset
3. Create the new list by traversing each element in hashset and creating links appropriately
4. Return his newly created list
public LinkedList<Node> LinkedListsUnion(Node root1, Node root2)
{
HashSet<int> elems= new HashSet<int>();
while(root1.Next != null)
{
elems.Insert(root1.Data);
root1=root1.Next;
}
while(root2.Next!=null)
{
elems.Insert(root2.Data);
root2=root2.Next;
}
LinkeList ll= new LinkedList();
foreach(int item in elems)
{
Node n= new Node(item);
if(ll.Root==null)
{
ll.Root=n;
}
else
{
Node temp=ll.root;
//Traverse till the end of the list
//to insert at last
// but since ordering is not important we can even
// change the head ptr to the new node
while(temp.Next==null)
temp=temp.Next;
temp.Next=n;
}
return ll;
}
@Shoonya Yes that solution works too and in fact it is better than my approach in which I am doing a linear search at the end. But he failed mention lots of important things so I didn't look at his solution seriously.
1. The columns must be increasing order, i.e. no element from column i+1 can be lesser than column i. (Transpose to my assumption).
2. The reason he started at 2,0.
As far as I see, this is a difficult problem. Even to traverse an array it takes O(n2) so its not simple to search an element in O(n). But I think I got some kind of solution, not sure if its O(n) though. Also one assumption we have to make is all the values below a row are greater than the current rows values. Otherwise there is no way we can find a solution less than O(n2).
Also to simplify further I considered only square matrices, since this solution is working it should not be super difficult to convert it into a non-square matrix.
My idea is search for the element on diagnol elements if not found narrow down to the two rows between which the element could exist. then perform a linear search on the rows. Since we are searching only two rows this should be O(n).
//Assuming that the matrix is square m=n
//Assuming no row i+1 has an element lower than i
The scaffold for the funtion:
int[,] mat3 = new int[,] { {1,2,3,4,5},
{6,7,8,9,10},
{11,12,13,14,15},
{16,17,18,19,20},
{21,22,23,24,25},
};
int[,] mat2 = new int[,] { {1,2,3,4},
{6,7,8,9},
{11,12,13,14},
{16,17,18,19},
};
int[] pos = p.Search2DSortedSquareMatrix(mat3, 3);
if(pos.Lenght==2)
Console.Write("x {0} y {1}", pos[0], pos[1]);
public int[] Search2DSortedSquareMatrix(int[,] mat, int x)
{
int[] op=new int[2];
int m = mat.GetLength(0);
int mid = m/2; //1 to get ceiling
bool minflag=false, maxflag=false;
int x1=0,y1=0;
while ((!minflag || !maxflag) && mid > 0 && mid < m)
{
if (mat[mid, mid] == x)
{
op[0] = mid; op[1] = mid;
return op;
}
else if (mat[mid, mid] < x)
{
minflag = true;
op[0] = mid;
mid++;
}
else if (mat[mid, mid] > x)
{
maxflag = true;
op[1] = mid;
mid--;
}
}
//Linear search this loop can further be improved but I am not able to figure out now.
for(int i=op[0];i<=op[1];i++)
for(int j=0;j<m;j++)
if (mat[i, j] == x)
{
op[0] = i; op[1] = j;
return op;
}
return null;
}
The interviewer sent me a reject and other than that he mislead during the interview. I should agree that I made some mistakes
1. I did not write down the structure of the block like I did now. This is important according to gayle
2. I had a frivolous bug that I was not able to uncover after running through with 3 test cases!! This shows lack of attention
3. I was returning only the first block along with the filename when the interviewer asked me to re-create the table explicitly. He could have pointed it out but it shows my lack of attention again.
Hopefully, I wont these mistakes again and land up in a job soon.
Actually to test this problem we need significant scaffolding. For those of whom are interested.
Lets assume we are a testing a Block b0->b8 such that
b1->b4->b7
b3->b2
b6->b5
b8
b0 is empty
public class Block
{
internal string Name { set; get; }
internal bool IsEmpty { set; get; }
internal Block NextBlock { set; get; }
public Block() { }
public Block(string name, bool isEmpty, Block nextBlock)
{
this.Name = name;
this.IsEmpty = isEmpty;
this.NextBlock = nextBlock;
}
public override string ToString()
{
return Name;
}
}
static void Main()
{
Block b8 = new Block("b8", false, null);
Block b7 = new Block("b7", false, null);
Block b5 = new Block("b5", false, null);
Block b6 = new Block("b6", false, b5);
Block b2 = new Block("b2", false, null);
Block b3 = new Block("b3", false, b2);
Block b4 = new Block("b4", false, b7);
Block b1 = new Block("b1", false, b4);
List<Block> harDisk = new List<Block>();
harDisk.Add(new Block("b0",true,null));
harDisk.Add(b1);
harDisk.Add(b2);
harDisk.Add(b3);
harDisk.Add(b4);
harDisk.Add(b5);
harDisk.Add(b6);
harDisk.Add(b7);
harDisk.Add(b8);
Dictionary<string, List<Block>> table = p.ReCreateTable(harDisk);
foreach (var item in table)
{
Console.Write(item.Key+ " ");
foreach (var block in item.Value)
Console.Write(block + " -> ");
Console.WriteLine()
}
}
This is the solution I came up with during the interview. There is one serious bug that I failed to uncover then and one consideration that I did not go through.
public Dictionary<string,List<Block> > ReCreateTable(List<Block> hardDisk)
{
int[] flags = new int[hardDisk.Count];
Dictionary<string, List<Block>> table = new Dictionary<string, List<Block> >();
for(int i=0;i<hardDisk.Count;i++)
{
if(hardDisk[i].IsEmpty)
{
flags[i]=2;
continue;
}
//This is the bug I had during the actual coding
//else if(hardDisk[i].NextBlock=null)
//flags[i]=0;
else if(hardDisk[i].NextBlock!=null)
{
Block temp=hardDisk[i];
while(temp.NextBlock!=null)
{
int num= (int)Char.GetNumericValue(temp.NextBlock.Name[temp.NextBlock.Name.Length-1]);
flags[num]=1;
temp=temp.NextBlock;
}
}
}
int cnt = 1;
for (int i = 0; i < flags.Length; i++)
{
if(flags[i]==0)
{
Block b=hardDisk[i];
string filename = "File" + cnt.ToString();
//During the interview I was only returning the first block of a //file. This is a better solution.
List<Block> fp = new List<Block>();
fp.Add(b);
while (b.NextBlock != null)
{
fp.Add(b.NextBlock);
b = b.NextBlock;
}
table.Add(filename, fp);
cnt++;
}
}
return table;
}
}
This solution seems to be working, though I have some shaky logic.
love to be proven wrong :)
//Assuming start and end gives the range inclusieve and we have primes given in hashset
//if not we need to create a hashset in the code
//Also end should be less than 101 since we are given only the first 100 primes
public List<int> GetAlmostPrimes(int start, int end, HashSet<int> primes)
{
List<int> almostPrimes = new List<int>();
for (int i = start; i < end; i++)
{
//if the number is already prime ignore it
if (!primes.Contains(i))
{
//An array to hold factors size is 4 to avoid out of bounds exception
int[] factors = new int[4];
int cnt = 0;
//We start from 2 because 1 is universal factor
//We end at i/2 because there will be no factors above the mid point of a number
for (int j = 2; j <= i / 2; j++)
{
if (cnt > 2) //Almost primes should have only 4 factors
break;
if (i % j == 0)
{
factors[cnt++] = j;
factors[cnt++] = i / j;
}
}
//Here we are banking on the fact that the first 2 factors of
//an almost prime should also be prime, otherwise automatically
//its not an almost prime eg. 12
//May be shaky logic but have to prove to be buggy to fix the bug :)
if (primes.Contains(factors[0]) && primes.Contains(factors[1]))
almostPrimes.Add(i);
}
}
return almostPrimes;
}
- prolific.coder May 18, 2010There is one small bug in the comparision logic of hashset. What happens if set2 is bigger than set1 and has an element that's not in set1? A simple fix would be compare the sizes of the sets first before entering the loop
- prolific.coder May 16, 2010"Here I have to assume that file ends with empty block." Its not a valid assumption. As I said in the problem definition, a file can be in just one block with its nextblock() pointing to null.
- prolific.coder May 15, 2010The pseudo-code looks good but imagine what it would have taken me to get to this solution and write code and test it during the interview. This is not the exact solution I got initially using similar data structures but somewhat different. But he wanted better, so there is more elegant solution that I came up with but even then the interviewer does not seem satisfied. Woof, so much for a tech screen!
- prolific.coder May 15, 2010Well for starters how can I get all the blocks of a file. The linked list is not constructed yet, we have to construct it. It would be very inefficient to fetch each block on demand, the list needs to be created before.
- prolific.coder May 15, 2010Yes, almost right. The interviewer actually explained this to me on the board so it was simpler :)
The table need not have filename as the key it just has the filename and the associated list of blocks. And the first blocks can know its following blocks through nextBlock. The challenge here is
F1 => n3->n5 // simple case
F2 => n7->n2->n1->n0 //complicated case
we have to reconstruct this table. And since in the node there is no way to identify the filename just assume that you can rename the files as you wish.
You need to reconstruct the table that holds the files and links. Different blocks can belong to different files.
- prolific.coder May 15, 2010None of the solutions above seem to be using the conditions given for their advantage. I got a 3 line solution, well it is O(n2) but that's what the interviewer asked for.
//If the matrix has no contents or all 1's return null
public int? FindRowWithMaxZeros(int[,] mat)
{
for (int j = 0; j < mat.GetLength(1); j++)//Traverse column wise second
for (int i = 0; i < mat.GetLength(0); i++)//But row wise first
//We are using the condition above that no 1 occurs after 0, so on seeing 0 we return that row
if (mat [i,j] == 0)
return i+1; //Return the row number after adding 1
return null;
}
- prolific.coder May 13, 2010public List<string> Tokenize(string input, string delimeters)
{
HashSet<char> delims = new HashSet<char>(delimeters);
List<string> strings = new List<string>();
StringBuilder sb = new StringBuilder();
foreach (char ch in input)
{
if (delims.Contains(ch))
{
if (sb.Length > 0)
strings.Add(sb.ToString());
sb.Clear();
}
else
sb.Append(ch);
}
if(sb.Length>0) //Required for the case when there is no delimeter at the end of the input string
strings.Add(sb.ToString());
return strings;
}
Though I am not super happy about the code and repeat of logic, right now I couldn't find any improvement.
Repmakaylamelua, Blockchain Developer at AMD
I am a sound editing and music composer with experience of handling a wide variety of programs.During my free ...
RepAlmaRJude, Quality Assurance Engineer at Brocade
I am Alma from Livermore USA, I also enjoy reading – my favourite topics being social history, the development and use ...
Reparlinenwalters, Software Analyst at ASAPInfosystemsPvtLtd
I Performed extensive web research to collect pertinent data and gather images related to the assigned articleIts act of writing ...
Rephallieriddic, HR Executive Trainee at Barclays Capital
I am Hallie, Dedicated and experienced administrative secretary who excels at prioritizing , completing multiple tasks simultaneously and following through to ...
Reploreleijhansen, Aghori Mahakal Tantrik at ABC TECH SUPPORT
I am Lorelei.I am working in a store as a Bonus clerk promoting the development, and implementation and solutions ...
Replouisefbray, Integration Software Engineer at Ask.com
Hey! My name is Louise and I am a computer hardware retailer and wholesaler.I also provide services online. My ...
1. Error checks - make sure m is not null and m has more than one element
- prolific.coder May 19, 20122. Iterate over M and populate the numbers sum into a variable sum.
3. let x = m.getlength(0) and y= m.getlength(1)
3. Create a new matrix out and populate out[x][y] with sum
4. Create a decreasing loop from x,y to 0,0 and populate with the following formula
out[i][j]=sum-m[i][j]