zsalloum
BAN USER 0of 0 votes
AnswersInsert a value into a sorted linked list.
 zsalloum in United States
Using C/C++ write a small function (around 5 lines in the body) to insert a value in a sorted linked list. Take into consideration that the list might be empty at first, and the function should cover the cases of insertion at the head and tail...
PS what the interviewer is looking for is the ability to write a small C/C++ code that solves the question and not the algorithm per se which is trivial Report Duplicate  Flag  PURGE
Microsoft Jr. Software Engineer C C# C++ Linked Lists
I see a straight forward solution.
If you have a dictionary or a list of words. You scan them make numeronym of each word. If the numeronym matches the given parameter or will be added to the result list.
At the end you return the result list.
Of course you can optimize by precomputing the numeronym of the dictionary for faster search.
The solution is to sort the array which will take nLog(n). Then take each element X in the sorted array subtract it from 12 such as int V = 12  X then since the array is sorted you can binary search for V in Log(n). To do so for the n elements it will take nLog(n).
So the final complexity will be O(nLog(n))
This is the second post as the first one does not seem to appear
You can also solve this using the "Hamming Weight" way (check wikipedia)
const char m1 = 0x55; //binary: 0101...
const char m2 = 0x33; //binary: 00110011..
const char m4 = 0x0f; //binary: 4 zeros, 4 ones ...
bool bitCount3(char x) {
x = (x & m1 ) + ((x >> 1) & m1 ); //put count of each 2 bits into those 2 bits
x = (x & m2 ) + ((x >> 2) & m2 ); //put count of each 4 bits into those 4 bits
x = (x & m4 ) + ((x >> 4) & m4 ); //put count of each 8 bits into those 8 bits
return x == 3;
}

zsalloum
April 13, 2015 I see this as constructing the truth table (roughly speaking)
Suppose we have AAAAAAAAA BBBB CC DDDDD E FFFF
We order it (as said before) by frequency:
A(9), D(5), B(4), F(4), C(2), E(1)
Then will construct the table starting with the most frequent char (in this case A). We fill it vertically, next we fill the second most frequent char and we continue with the remaining ones. example:
ADF
ADF
ADF
ADF
ADC
ABC
ABE
AB
AB
Now we concatenate all the lines of the table to have the required string:
ADFADFADFADFADCABCABEABAB
I don't have the mathematical proof for this, but as justification you can say, as long as you have a char that can be placed in the column next to the most frequent char you will be able to separate two similar chars.
Here is a C# example
using System.IO;
using System;
using System.Text;
using System.Collections.Generic;
class Program
{
class Entry{
public char Ch;
public int Freq;
}
static void Main()
{
String s = FancyShuffle("AAAAAABBBCCCDDDDDDDDDDFFFFF");
Console.WriteLine(s);
}
static String FancyShuffle(String s){
List<Entry> ls = ComputeFrequency(s);
StringBuilder[] rows = new StringBuilder[ls[0].Freq];
int r = 0;
for(int i = 0; i < ls.Count; i++){
Entry e = ls[i];
for(int k = 0; k < e.Freq; k++){
if(rows[r] == null) rows[r] = new StringBuilder();
rows[r].Append(e.Ch);
r = (r + 1) % rows.Length;
}
}
StringBuilder sb = new StringBuilder();
foreach(StringBuilder row in rows){
sb.Append(row);
}
return sb.ToString();
}
static List<Entry> ComputeFrequency(String s){
Dictionary<char, Entry> dic = new Dictionary<char, Entry>();
for(int i = 0; i < s.Length; i++){
if(dic.ContainsKey(s[i])){
dic[s[i]].Freq += 1;
}else{
Entry e = dic[s[i]] = new Entry();
e.Freq = 1;
e.Ch = s[i];
}
}
List<Entry> lst = new List<Entry>(dic.Values);
lst.Sort((e1, e2)=>{return e2.Freq  e1.Freq;});
return lst;
}
}

zsalloum
April 10, 2015 I will consider the most optimal case which is the marking are equally spaced.
So let L be the distance between two consecutive marking. N will then be equal to (M+1)*L.
The best way to cut in this case is to cut at the marking M/2, then M/4, etc...until we reach L
This cutting path costs Log(N), since there are M similar paths. The total cost will be M*Log(N).
This solution is better than cutting the markings in sequence starting with the 1st, then 2nd, then 3rd until Mth. Which results in a cost of (M+1)*N/2
However since we don't know if the markings are equally spaced, the best solution is to try to get as close as possible to the optimal one (explained above) by cutting at the marking which is the closest to the middle of the segment.
Doing the sum of each number with the rest of numbers in the array will result in O(n^2).
To do better, you need to sort the array with a sorting criteria Abs(number) this will complete in O(nlog(n))
and will give a result like the following:
10, 50, 20, 1, 2 , 5, 51, 70 => 1, 2, 5, 10, 20, 50, 51, 70
Now adding each two consecutive numbers will take O(n1) and will result in finding 50 and 51 as having the closest sum to zero
Total cost of the operation is n(1 + log(n)) which is way less than O(n^2)
It is also possible to optimize this further, by checking (while sorting) if the array contains only positive or negative numbers.
In this case the closest sum to zero is guaranteed to be the first 2 numbers in the sorted array
Open Chat in New Window
I have been asked this question some 15 years ago and amazingly even today I don't see clean solution for it on the internet. This is why I posted here.
The right solution is this. Pay attention how the insert method is simple and concise:
The output is:
 zsalloum May 03, 20150, 5, 10, 15, 18, 20, 25, 40, 50, 100